import copy


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def allPossibleFBT(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        out = []
        tree = TreeNode()
        st = [tree]

        def search(st, k):
            if k == n:
                out.append(copy.deepcopy(tree))
            else:
                if k < n:
                    count = len(st)
                    value = 1 << count
                    for t in range(1, value):
                        next_k = k
                        next_st = []
                        for j in range(count):
                            if (t >> j) & 1 == 1:
                                next_k += 2
                                st[j].left = TreeNode()
                                st[j].right = TreeNode()
                                next_st.append(st[j].left)
                                next_st.append(st[j].right)
                        search(next_st, next_k)
                        for j in range(count):
                            if (t >> j) & 1 == 1:
                                st[j].left = None
                                st[j].right = None

        search(st, 1)
        return out




